#include <stdio.h>
#include <stdlib.h>
#include "sort.h"
#include "list.h"

static void Swap(T *a, T *b)
{
        T tmp = *a;
        *a = *b;
        *b = tmp;
}

void InsertSort(sqlist list, int n)
{
//老师的写法
#if 0
        for (int i = 1; i < n; ++i)
        {
                if (list[i] < list[i - 1])
                {
                        Swap(&list[i], &list[i - 1]);
                        for (int j = i - 1; j > 0 && list[j] < list[j - 1]; --j)
                                Swap(&list[j], &list[j - 1]);
                }
        }
#endif

//我的写法(本质上和老师的相同)
#if 0
        for (int i = 1; i < n; ++i)
        {
                for (int j = i; j > 0; j--)
                {
                        if (list[j] < list[j - 1]) //后一个比前一个小，交换
                                Swap(&list[j], &list[j - 1]);
                        else
                                break;
                }
        }
#endif

//第三种写法(本质和上两种不同，上两种是不断交换，这种是移动元素
//(将大于待排序元素的元素不断后移，直到找到给定元素应该插入的位置)
#if 1
        for (int i = 1; i < n; ++i)
        {
                int temp = list[i], j = i; // temp为需要插入的值
                for (; j > 0; j--)
                {
                        if (temp < list[j - 1])   //temp比前一个值小
                                list[j] = list[j - 1];
                        else
                        {
                                list[j] = temp;
                                break;
                        }
                }
                if (j == 0)
                        list[0] = temp;

                printf("第%d次循环后：", i);
                for (int i = 0; i < n; i++)
                        printf("%d ", list[i]);
                printf("\n");
        }
#endif
}

void BInsertSort(sqlist list, int n)
{
        int low, high, mid;

        for (int i = 2; i < n; i++)
        {
                list[0] = list[i];   //0位置用于保存待排序元素
                low = 1;
                high = i - 1;
                while (low <= high)
                {
                        mid = (low + high) / 2;

                        if (list[0] >= list[mid])
                                low = mid + 1;
                        else
                                high = mid - 1;
                }
                // while循环结束后：low=high+1
                for (int j = i; j >= low; --j)
                        list[j] = list[j - 1];
                list[low] = list[0];
        }
}

void TWayInsertSort(sqlist list, int n)
{
        sqlist tmp;
        int head, tail;

        tmp[0] = list[0]; //将第一个元素放入辅助空间
        head = tail = 0;

        for (int i = 1; i < n; i++)
        {
                if (list[i] <= tmp[head])
                {
                        head = (head - 1 + n) % n;
                        tmp[head] = list[i];
                }
                else if (list[i] >= tmp[tail])
                {
                        tail++;
                        tmp[tail] = list[i];
                }
                else //既不小于头也不大于尾，此时需要移动数据
                {
                        tail++;
                        // tmp[tail] = tmp[tail - 1];
                        int j;
                        for (j = tail; list[i] < tmp[(j - 1 + n) % n];)
                        {
                                tmp[j] = tmp[(j - 1 + n) % n];
                                j = (j - 1 + n) % n;
                        }
                        tmp[j] = list[i];
                }
        }

        for (int i = 0; i < n; i++)
        {
                list[i] = tmp[head];
                head = (head + 1) % n;
        }
}

void TableInsertSort(Table tb, int n)
{
        int p, q;

        tb[0].link = 1; //初始设置第一个元素为最小值，形成一个循环链表
        for (int i = 2; i < n; i++)
        {

                p = tb[0].link; // p指示最小值的下标
                q = 0;          // p的前驱,初始为最小值的前驱：最大值的下标
                while (p != 0 && tb[i].data >= tb[p].data)
                {
                        q = p;
                        p = tb[p].link; // p修改为次小值的下标
                }
                //此时：tb[q] < tb[i] < tb[p],把tb[i]插入在tb[q]之后
                tb[i].link = tb[q].link;
                tb[q].link = i;
        }
}

static void ShellInsert(sqlist list, int n, int dk)
{
//老师的写法
#if 0
        for (int i = dk + 1; i < n; i++)
        {
                if (list[i] < list[i - dk]) //后一个比前一个小
                {
                        list[0] = list[i];   //list[0]保存后一个的值
                        int j;
                        for (j = i - dk; j > 0 && list[0] < list[j]; j -= dk)
                        {
                                list[j + dk] = list[j];
                        }
                        list[j + dk] = list[0];
                }
        }
#endif

//我的写法(不需要使用list[0])
#if 0
        for (int i = 1; i <= dk; i++) //分成dk组
        {
                int j = i + dk;
                while (j < n)
                {
                        for (int k = j; k > 0; k -= dk)
                        {
                                if (list[k] < list[k - dk])
                                        Swap(&list[k], &list[k - dk]);
                                else
                                        break;
                        }
                        j += dk;
                }
        }
#endif

//第三种写法(本质和上两种不同，上两种是不断交换，这种是移动元素
//(将大于待排序元素的元素不断后移，直到找到给定元素应该插入的位置)
#if 1
        for (int i = 0; i <= dk; i++) //分成dk组
        {
                int t = 1;
                for (int j = i + dk; j < n; j += dk)
                {
                        int temp = list[j]; // temp为待排序元素
                        int k = j - dk;
                        for (; k >= i; k -= dk)
                        {
                                if (temp < list[k])
                                        list[k + dk] = list[k];
                                else
                                {
                                        list[k + dk] = temp;
                                        break;
                                }
                        }
                        if (k < i)
                                list[i] = temp;
                        printf("增量为%d,第%d次循环后：", dk, t++);
                        for (int i = 0; i < n; i++)
                                printf("%d ", list[i]);
                        printf("\n");
                }
        }
#endif
}

void ShellSort(sqlist list, int n, int *dlta, int t)
{
        for (int i = 0; i < t; ++i)
                ShellInsert(list, n, dlta[i]);
}

void BubbleSort(sqlist list, int n)
{
        for (int i = 1; i < n; i++)
        {
                int flag = 1;
                for (int j = 1; j <= n - i; j++)
                {
                        if (list[j] < list[j - 1])
                        {
                                Swap(&list[j], &list[j - 1]);
                                flag = 0;             
                        }
                }
                if (flag == 1)   //本趟遍历后没有发生交换，说明表已经有序，程序可以提前结束。
                        return;
        }
}

static int Partition(sqlist list, int low, int high)
{
        T pk = list[low]; //使用临时空间保存pk值，这里选择了序列中的第一个元素作为pk值
        while (low < high)
        {
                while (low < high && list[high] >= pk)
                        high--;
                list[low] = list[high];
                while (low < high && list[low] <= pk)
                        low++;
                list[high] = list[low];
        }
        list[low] = pk; // pk值放回
        return low;     //返回分界点
}

static int partition(sqlist list, int low, int high, int pk)
{
#if 0
        //我写的，pk取值有bug,只能取low(其实无论取哪个位置作为分界值，都可以将该位置的值与low位置的值交换，进而转化为low位置的值作为分界值)
        if (pk != low)
        {
                Swap(&list[low], &list[pk]);
                pk = low;
        }
        int cter = list[pk]; //分界值
        while (low < high)
        {
                while (low < high && list[high] >= cter)
                        high--;
                list[pk] = list[high];
                pk = high;
                while (low < high && list[low] <= cter)
                        low++;
                list[pk] = list[low];
                pk = low;
        }
        list[pk] = cter; // pk值放回
        return pk;       //返回分界点
#endif

//书上的写法，感觉不错
#if 0
        int pk = low;
        int cter = list[low];   //记录分界值
        for (int i = low + 1; i <= high; i++)
        {
                if (list[i] < cter)
                {
                        pk++;   //pk指向的值总是<=cter
                        if (pk != i)
                                Swap(&list[pk], &list[i]);  //把小的值换到左边，大的值换到右边
                }
        }
        list[low] = list[pk];  //把比cter小的值放到左边
        list[pk] = cter;       //把分界值放到中间
        return pk;
#endif

// 王道的写法
#if 1
        int i = 0, n = high - low + 1, pivot = list[low];   //第一个元素作为基准元素
        while (low < high)
        {
                while (low < high && list[high] >= pivot)
                        --high;
                list[low] = list[high];

                printf("第%d次交换：", ++i);
                for (int i = 0; i < n; i++)
                        printf("%d ", list[i]);
                printf("\n");

                while (low < high && list[low] <= pivot)
                        ++low;
                list[high] = list[low];

                printf("第%d次交换：", ++i);
                for (int i = 0; i < n; i++)
                        printf("%d ", list[i]);
                printf("\n");
        }
        list[low] = pivot;   //基准元素存放到最终位置
        return low;    //返回存放基准元素的最终位置
#endif
}

void QuickSort(sqlist list, int low, int high)
{
        if (low < high)
        {
                int pkloc = partition(list, low, high, high);
                QuickSort(list, low, pkloc - 1);
                QuickSort(list, pkloc + 1, high);
        }
}

void SelectSort(sqlist list, int n)
{
        int min, pos;

        for (int i = 0; i < n - 1; i++)
        {
                min = list[i]; //假设list[i]为最小值
                pos = i;       //最小值下标为i
                for (int j = i + 1; j < n; j++)
                {
                        if (list[j] < min)
                        {
                                min = list[j];
                                pos = j; //修改最小值下标
                        }
                }
                printf("min = %d\n", min);
                if (pos != i)
                        Swap(&list[i], &list[pos]);
        }
}

static T GetValue(T *tree, int size, int p)
{
        if (p >= size)
                return MAXVALUE;

        T value;
        if (p < size / 2) // tree[p]存储的是下标，需两次取值
                value = tree[tree[p]];
        else // tree[p]存储的是值
                value = tree[p];
        return value;
}

static void Play(T *tree, int size, int p)
{
        int left, right;
        T leftvalue, rightvalue;

        //存储数据的下标而不是数据本身(因为得到最小值时我们要修改该值，存储下标就方便找到该结点)
        while (p >= 0)
        {
                left = 2 * p + 1;  //左子树下标
                right = 2 * p + 2; //右子树下标
                leftvalue = GetValue(tree, size, left);
                rightvalue = GetValue(tree, size, right);
                if (leftvalue <= rightvalue) //左子树值<右子树值.如果左子树中存储的是下标，则保存左子树的值，否则保存左子树的下标
                {
                        if (left < size / 2)          // left不属于叶子结点
                                tree[p] = tree[left]; //保存左子树中的值
                        else                          // left属于叶子结点
                                tree[p] = left;       //保存左子树的下标
                }
                else
                {
                        if (right < size / 2)
                                tree[p] = tree[right]; //保存右子树中的值
                        else
                                tree[p] = right; //保存右子树的下标
                }
                --p;
        }
}

static void Select(T *tree, int size, int p)
{
        int parent = p;  // parent
        int left, right; // leftchild,rightchild
        T leftvalue, rightvalue;
        int flag = 1;

        while (flag && parent >= 0)
        {
                left = 2 * parent + 1;
                right = left + 1;
                leftvalue = GetValue(tree, size, left);
                rightvalue = GetValue(tree, size, right);

                if (leftvalue <= rightvalue)
                {
                        if (left < size / 2)
                                tree[parent] = tree[left];
                        else
                                tree[parent] = left;
                }
                else
                {
                        if (right < size / 2)
                                tree[parent] = tree[right];
                        else
                                tree[parent] = right;
                }

                if (parent == 0)
                        flag = 0;
                parent = (parent - 1) / 2; // parent变为它自己的父节点
        }
}

void TreeSelectSort(sqlist list, int n)
{
        int size = 2 * n - 1; //树形结构结点数
        int k = size / 2;     // list[0]在tree数组中存放的下标
        int curpos = k - 1;   //第一个待计算的结点

        //分配内存
        T *tree = malloc(sizeof(size * sizeof(T)));
        //给tree的叶子赋值
        for (int i = 0; i < n; i++)
                tree[k++] = list[i];
        //开始比较，得出最小值
        Play(tree, size, curpos);
        list[0] = tree[tree[0]];
        tree[tree[0]] = MAXVALUE;
        //计算余下的n-1个结点
        for (int i = 1; i < n; ++i)
        {
                curpos = (tree[0] - 1) / 2;
                Select(tree, size, curpos);
                list[i] = tree[tree[0]];
                tree[tree[0]] = MAXVALUE;
        }
        free(tree);
}

static void siftDown(T *heap, int n, int curpos)
{
        int parent = curpos;     //父结点下标(待排序数组从0开始存储的)
        int left = 2 * parent + 1;   //左孩子下标(待排序数组从0开始存储的)
        int right = left + 1;       //右孩子下标

        while (left < n) //左子树存在
        {
                if (left < n - 1 && heap[left] > heap[right]) //右子树存在且左子树的值大于右子树
                        left++;
                if (heap[parent] <= heap[left])    //父结点值小于孩子结点的值不需要调整
                        break;
                else
                {
                        Swap(&heap[parent], &heap[left]);
                        parent = left; //调整之后还要看下面是否仍然是小根堆
                        left = 2 * parent + 1;
                        right = left + 1;
                }
        }
}

static T RemoveMinKey(T *heap, int n)
{
        T key = heap[0];      //保存堆顶元素
        heap[0] = heap[n];    //将最后一个元素移至堆顶
        siftDown(heap, n, 0); //再次调整
        return key;           //返回最小值
}

void HeapSort(sqlist list, int n)
{
        T *heap = malloc(sizeof(T) * n); //可以直接针对list调整而不用分配内存
        for (int i = 0; i < n; i++)
                heap[i] = list[i];
        //找到最后一个分支节点,建立堆
        int curpos = n / 2 - 1;
        while (curpos >= 0)
        {
                siftDown(heap, n, curpos);
                --curpos;
        }
        for (int i = 0; i < n; i++)
                list[i] = RemoveMinKey(heap, n - i - 1); //移出堆顶元素
        free(heap);
}

static void Merge(sqlist list, sqlist tmp, int left, int mid, int right)
{
        int p, q, k;

        for (int i = left; i <= right; ++i)
                tmp[i] = list[i];    //初始化辅助数组
        p = left;
        q = mid + 1;
        k = left;
        while (p <= mid && q <= right)
        {
                if (tmp[p] <= tmp[q])
                        list[k++] = tmp[p++];
                else
                        list[k++] = tmp[q++];
        }
        while (p <= mid) //左半边元素未合并完
                list[k++] = tmp[p++];
        while (q <= right) //右半边元素未合并完
                list[k++] = tmp[q++];
}

void MergeSort(sqlist list, sqlist tmp, int left, int right)
{
        if (left >= right)
                return;
        int mid = (left + right) / 2;        //从中间划分
        MergeSort(list, tmp, left, mid);      //归并排序左半部分
        MergeSort(list, tmp, mid + 1, right); //归并排序右半部分
        Merge(list, tmp, left, mid, right);   //合并左右两个有序序列
}

static T getkey(T value, int k)
{
        while (--k >= 0)
                value /= 10;
        return value % 10;
}

static void Distribute(sqlist L, int n, int k, list **tp)
{
        int key;

        for (int i = 0; i < n; i++)
        {
                key = getkey(L[i], k);
                list_insert_backword(&tp[key], &L[i]);
        }
}

static void Connect(sqlist L, list **tp, int n)
{
        int k = 0;
        list *p;
        for (int i = 0; i < n; i++)
        {
                p = tp[i];
                while (p != NULL)
                {
                        L[k++] = p->data;
                        p = p->next;
                }
        }
        for (int i = 0; i < n; i++)
                list_destory(&tp[i]); //将链表恢复原状
}

void RadixSort(sqlist L, int n)
{
        list *t[n]; //这里我们使用的是Data_Structure/list/nohead文件夹下的无头单链表(list.c list.h)
        for (int i = 0; i < n; i++)
                t[i] = NULL;
        for (int i = 0; i < 3; ++i)
        {
                Distribute(L, n, i, t);
                Connect(L, t, n);
        }
}